1. Field of Invention
The present invention relates generally to data communication systems. More particularly, the present invention relates to systems and methods for substantially automating the computation of a circuit path between two nodes that includes specified network elements and network links.
2. Description of the Related Art
The demand for data communication services is growing at an explosive rate. Much of the increased demand is due to the fact that more residential and business computer users are becoming connected to the Internet. Furthermore, the types of traffic being carried by the Internet are shifting from lower bandwidth applications towards high bandwidth applications which include voice traffic and video traffic.
To address the demand for data communication services, the use of optical networks, such as a synchronous optical network (SONET) is becoming more prevalent. One type of SONET network, or one type of network that is subject to SONET standards is a time division multiplexing (TDM) network. TDM networks generally allocate single channels or lines to be used amongst multiple users, or customers of data communication services. The single channels may each be divided into slots of time during which each user has access to the single channels. In general, the availability of a link between nodes for consideration as a part of a circuit path requires that TDM bandwidth is available on that link for the circuit being routed.
A network such as a TDM network is generally designed to ensure that information may be transferred between nodes within the network. Often, within a network, information is transferred between two specified nodes, i.e., a source node which sends information and a destination node which receives information. When information is to be sent between a source node and a destination node, a circuit path between the two nodes must be computed so that leased line services may be provided. FIG. 1 is a diagrammatic representation of a network in which leased line services may be provided. A network 104 includes nodes 108 and links 112. Nodes 108 include a source node A 108a and a destination node Z 108z. In order for information to be sent from source node A 108a to destination node Z 108z, a circuit path between source node A 108a and destination node Z 108z must be identified.
A routing algorithm is generally used to route a path between source node A 108a and destination node Z 108z, once source node A 108a and destination node Z 108z have been identified, e.g., by a network administrator. Often, a routing algorithm which routes a path between source node A 108a and destination node Z 108z is a shortest path first algorithm which identifies the shortest path, or the path which includes the fewest nodes, between source node A 108a and destination node Z 108z. As shown, a path 116 that is routed between source node A 108a and destination node Z 108z is the shortest path between source node A 108a and destination node Z 108z. Hence, leased line services may be provided using path 116.
At times, in order to provide new services or to balance the load within a network such as network 104, a network administrator may wish to create circuits which are required to traverse specific nodes or links. As will be appreciated by those skilled in the art, certain nodes may be specified as being required when drops are to be added at the nodes, while certain links may be specified as being required to balance the load within a network. FIG. 2 is a diagrammatic representation of a network in which two particular nodes are required to be accessible from a third node. A network 204 includes nodes 208 and links 212. Nodes 208 include source node A 208a, as well as node C 208c and node F 208f which are to be traversed. Specifically, a circuit path is to first traverse node F 208f before reaching node C 208c, which may be considered to be a destination node.
If a conventional shortest path first algorithm is to be used to access node A 208a, node F 208f, and node C 208c, a network administrator typically may specify that a circuit path 216 between node A 208a and node F 208f be created, then that a circuit path 218 between node A 208a and node F 208f be created. The use of individual paths 216, 218 is generally not acceptable when node F 208f is to be used as a drop between node A 208a and node C 208c. That is, a conventional shortest path first algorithm is generally not capable of creating a path given a criterion which specifies that an “intermediate” node 208 or link 212 must be traversed when a path between node A 208a and node C 208c is created.
In order to route a path 220 between node A 208a and node C 208c which includes a required element such as node F 208f, a network administrator must manually create path 220. In creating path 220, the network administrator manually routes segment 220a between node A 208a and node F 208f, then routes segment 220b between node F 208f and node C 208c. 
Manually routing a path between a source node and a destination node is time consuming and, hence, inefficient, particularly in large networks. Further, when a path is manually routed, the likelihood that the path is routed incorrectly increases. For example, although a shortest available path may be desired, human error may result in a manually routed path not being the shortest path between the source node and the destination node that includes required elements. Such an error may cause an overall network to operate inefficiently. Manually routing a path may also result in paths which erroneously mix protected links with unprotected links, or paths which traverse required elements in an incorrect order.
Therefore, what is needed is an efficient method and apparatus for creating circuit paths which include required elements. That is, what is desired is an efficient system which enables circuit paths that traverse required elements in a specified order to be created substantially automatically.